import java.util.Arrays;
import java.util.Stack;




//155. 最小栈
//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//实现 MinStack 类:
//MinStack() 初始化堆栈对象。
//void push(int val) 将元素val推入堆栈。
//void pop() 删除堆栈顶部的元素。
//int top() 获取堆栈顶部的元素。
//int getMin() 获取堆栈中的最小元素。
class MinStack {
//    创建两个栈  一个是标准栈 另一个存放最小值栈
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {//构造
        stack = new Stack<>();
        minStack = new Stack<>();
    }
//      存入栈
    public void push(int val) {
        stack.push(val);//标准栈直接存
        if (minStack.empty()) {//最小值栈为空 存
            minStack.push(val);
        }else {
//            最小值栈不为空 判断 最小值栈top顶是否<=存入标准栈的值
            int top = minStack.peek();
            if (val <= top) {
                minStack.push(val);
            }
        }
    }
//      标准栈直接pop  如果最小值栈top等于删除的值 那么也删除
    public void pop() {
        int oldVal = stack.pop();
        int top = minStack.peek();
        if (oldVal == top) {
            minStack.pop();
        }
    }
//  查看标准栈顶元素
    public int top() {
        return stack.peek();
    }
//  查看最小栈栈顶元素
    public int getMin() {
        return minStack.peek();
    }
}


public class StackQuestions {

    //    150. 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
//        tokens.length求  字符串数组的长度 遍历每一个元素
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if (!isOperator(str)) {
                stack.push(Integer.parseInt(str));//将字符串类型转换为int类型
            }else {
//                取出第一个放运算符右边  第二个放运算符左边
                int num2 = stack.pop();
                int num1 = stack.pop();
//                判断是哪种运算符
                switch (str) {
                    case "+":
                        stack.push(num1+num2);
                        break;//break 不能忘
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    //    是否是+ — * / 运算符
    public boolean isOperator(String str) {
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
            return true;
        }
        return false;
    }



    //    31. 栈的压入、弹出序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        i遍历pushed   j遍历popped
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);//放入栈中
            while (j < popped.length && !stack.empty() && stack.peek() == popped[j]) {
                stack.pop();//满足条件取出
                j++;
            }
        }
        return stack.empty();
    }


//    20. 有效的括号
//    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//有效字符串需满足：
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
//            如果是左括号 直接入栈
            if (ch=='{' || ch=='[' || ch=='(') {
                stack.push(ch);
            }else {
//                遇到右括号
                if (stack.isEmpty()) {//判断栈是否为空
//                    右括号多
                    System.out.println("右括号多");
                    return false;
                }
                char top = stack.peek();//其中一个左括号
                if (top=='['&&ch==']' || top=='{'&&ch=='}' || top=='('&&ch==')') {
                    stack.pop();
                }else {
//                    左右括号不匹配
                    System.out.println("左右括号不匹配");
                    return false;
                }
            }
        }
//        for走完 但是栈中还有括号
        if (!stack.isEmpty()) {
            System.out.println("左括号多");
            return false;
        }
        return true;
    }



}
